package _11_整理题目._1_链表指针._环节点;

import org.junit.Test;
import util.ListNode;

/**
 * 对于一个给定的链表，返回环的入口节点，如果没有环，返回null
 * 
 * 实际要做两件事，第一件判断是否有环，第二件有环了如何找到交点
 * 有环的话，重置 fast=head，fast和slow每次走一步，while至再次相遇即为交点
 * 
 */
public class _02_链表中环的入口节点 {
    
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null && fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                fast = head;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }
    
    @Test
    public void main() {
        Integer[] array = {1, 2, 3, 4};
        ListNode head = ListNode.getListFromArray(array);
        System.out.println(detectCycle(head));
        
        head.next.next = head.next;
        System.out.println(detectCycle(head).val);
    }
}
